#include <iostream>
#include <vector>
#include "BinarySearchTree.h"


template <class Comparable>
void BSTSorting( std::vector<Comparable> &_arr, int _mode = 0 )
{

  
  /*防止处理空树*/
  if( _arr.size() == 0)
    {
      std::cout << "您输入的数组为空" << std::endl;
      return ;
    }


  
  /*对数组打乱后排序*/
  if( _mode == 1)
    {
      std::cout << "\n将数组打乱" << std::endl;
    for (int i = 0; i < _arr.size(); i++)
    {
    int r = i + rand() % ( _arr.size() - i);
    swap( _arr[i], _arr[r]);
    }

    
   /*输出打乱后的数组*/
    int shuchu = 0; 
    std::cout << "要不要输出乱顺序数组? 要就扣1,不要扣0." << std::endl;
    std::cin >> shuchu;
    if(shuchu != 1 && shuchu != 0 ){
      std::cout <<"输错数字了。默认不输出" << std::endl;
      shuchu = 0;
    }
    if(shuchu){
    std::cout << "打乱后的数组" << '\n';
     for( vector<int>::iterator itr = _arr.begin();
       itr != _arr.end();
       itr++)
    {
      std::cout << *itr << '\t';
      
    }
     std ::cout << '\n';
    }
      _mode = 0 ;
      BSTSorting( _arr , _mode );
      return ;
    }

  

  /*给数组排序*/
  BinarySearchTree<Comparable> T;
  for( int j =0 ; j < _arr.size(); j++ )
    {
      T.insert( _arr[j] ); 
    }
  vector<Comparable> arr_temp;
  while( !T.isEmpty() )
    {
      arr_temp.push_back( T.findMin() );
      T.remove( T.findMin() );
    } //默认从大到小来排序         
  arr_temp.swap( _arr );


  
  return;
}
